import java.util.LinkedList;
import java.util.Queue;

public class Binarytree {
    public static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        //连接起来
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.left = H;
        return A;
    }
    public void preOrder(TreeNode root){//前序遍历
        if(root == null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }
    public void inOrder(TreeNode root){//中序遍历
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    public void postOrder(TreeNode root){//后序遍历
        if(root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

    //求节点数方法一
    public int nodeSize=0;
    public void Size(TreeNode root){
        if(root == null){
            return;
        }
        nodeSize++;//不为空就累加
        Size(root.left);
        Size(root.right);
    }

    //求节点数方法二
    public int Size2(TreeNode root){
        if(root == null){
            return 0;
        }
        return Size2(root.left) + Size2(root.right) + 1;
    }
    //求叶子数方法一
    public int getLeafNodeCount(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left==null &&root.right==null){
            return 1;
        }
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }
    //求叶子数方法二
    public int LeafSize=0;
    public void getLeafNodeCount2(TreeNode root){
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null){
            LeafSize++;
        }else {
            getLeafNodeCount2(root.left);
            getLeafNodeCount2(root.right);
        }
    }

    //求k层节点个数
    //思路：整棵树的第k层=左子树的k-1层+右子树的k-1层，当k==1时说明找到了这一层
    public int getKLevelNodeCount(TreeNode root, int k){
        if(root==null){
            return 0;
        }
        if(k==1) {
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }

    //求高度
    public int getHeight(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHight=getHeight(root.left);
        int rightHight=getHeight(root.right);
        return Math.max(leftHight,rightHight)+1;
    }

    //检查value的值是否存在
    public TreeNode find(TreeNode root, int val){
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
        TreeNode findret=find(root.left,val);
        if(findret!=null){
            return findret;//左树找到了
        }
        findret=find(root.right,val);
        if(findret!=null){
            return findret;//右树找到了
        }
        return null;
    }
    //层序遍历
    public void levelOrder(TreeNode root){
        if(root==null){
            return;
        }
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            System.out.print(cur.val+" ");
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
    }



    //判断两棵树是否一样
    public boolean isSameTree(TreeNode root1,TreeNode root2){
        if(root1==null&&root2!=null||root1!=null&&root2==null){
            return false;
        }
        if(root1==null&&root2==null){
            return true;
        }
        if(root1.val!=root2.val){
            return false;
        }
        return isSameTree(root1.left,root2.left)&&isSameTree(root1.right,root2.right);
    }
//    public TreeNode invertTree(TreeNode root) {
//        if(root==null){
//            return null;
//        }
//        TreeNode left=invertTree(root.left);
//        TreeNode right=invertTree(root.right);
//        root.left=right;
//        root.right=left;
//        return root;
//    }

//    public boolean isSymmetric(TreeNode root){
//        if(root==null){
//            return true;
//        }
//        return isSymmetriChild(root.left,root.right);
//    }
//    public boolean isSymmetriChild(TreeNode leftTree, TreeNode rightTree){
//        if(rightTree==null&&leftTree!=null||rightTree!=null&&leftTree==rightTree){
//            return false;
//        }
//        if(leftTree==null&&rightTree==null){
//            return true;
//        }
//        if(leftTree.val!=rightTree.val){
//            return false;
//        }
//        return isSymmetriChild(leftTree.left,rightTree.right);
//    }
}
